import java.util.Scanner;


public class mergeSort {

	/**
	 * @param args
	 */
	static void mergeSort(int p, int r, int [] a){
		if(p==r){
			return;
		}
		int m = (p+r)/2;
		mergeSort(p, m, a);
		mergeSort(m+1, r, a);
		int [] left = new int [m-p+1];
		int [] right = new int [r-m];
		for (int i =p; i<m; i++)
		{
			left[i-p]=a[i];
		}
		for (int i =m+1; i<r; i++)
		{
			right[i-(m+1)]=a[i];
		}
		int [] res= merge(left,right);
		for (int i=0; i<res.length; i++)
		{
			a[i+p]=res[i];
		}
	}
	
	
	static int [] merge (int [] a, int [] b){
		int i=0, j=0, k=0;
		int c[]= new int [a.length+b.length];
		while (i<a.length && j<b.length){
			if(a[i]< b[j])
			{
				c[k]=a[i];
				i++;
			}
			else {
				c[k]= b[j];
				j++;
			}
			k++;
		}
		if(i==a.length){
			for(;j<b.length; j++)
			{
				c[k]= b[j];
				k++;
			}
			
		}
		else {
			c[k]=a[i];
			k++;
		}
		return c;
		
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner (System.in);
		System.out.print("Size a: ");
		int n = sc.nextInt();
		int a[]= new int [n];
		for (int i=0; i<a.length;i++)
		{
			System.out.print("Element a: ");
			a[i]=sc.nextInt();
		}
		mergeSort(0, a.length-1, a);
		for (int i=0; i<a.length; i++)
			System.out.print(a[i]);
		

	}

}
